1. Field of the Invention
The present invention relates generally to next generation wireless communication systems; and more particularly, to scheduling users in communication systems for allocating transmitted data to these users.
2. Description of Related Art
New technical challenges emerge as telecommunication systems evolve from a second generation system offering pure voice services, to a third generation system providing mixed voice and data services. In meeting data service demands, new performance metrics and algorithms need to be defined in order to optimize data performance.
CDMA 3G-1x Evolution Data Only (1xEVDO or known as High Data Rate) system is an evolution system of cdma2000 3G-1x system, and is a pure data system to provide data services to mobile users. In 1xEVDO, a scheduler or scheduling function is provided in a base station controller in order to provide fast scheduling or management of system resources based on channel quality feedback from one or more mobiles. In general, a scheduler selects a mobile for transmission at a given time instant, and adaptive modulation and coding allows selection of the appropriate transport format (modulation and coding) for the current channel conditions seen by the mobile.
In second generation wireless communications systems such as those of the IS-95 standard, applications typically employ voice-based communication schemes, in which a connection between the base station and the mobile is a dedicated connection. Since these are essentially fixed connections, there is no need for prioritizing the order of transmission to the active users served by the system (an active user is a user with data to transmit at a current time instant). However, with the emergence of third generation wireless data communications systems, such as CDMA-2000 standard systems and 1xEVDO, management of system resources is paramount. This is because properties of data differ significantly from properties of voice. For example, a data transmission, unlike a voice transmission, is not necessarily continuous and may be embodied as a burst transmission or an intermittent-type transmission between a base station and a mobile, for example. Accordingly, a base station in a third-generation system will attempt to manage a large pool of data users by assigning radio resources to each user for transmission. Typically this is done utilizing a prioritization scheme controlled by a scheduler in the base station controller. In a conventional prioritization scheme, idle mobile's are assigned a lower priority than mobile with data to transmit.
Accordingly, the scheduler must be able to manage these large numbers of users without wasting radio resources of the communication system. This management function becomes even more important as a base station attempts to meet QoS (Quality of Service) requirements. QoS is a general term that may represent a number of different requirements. As a basic tenant, QoS is indicative of providing guaranteed performance (e.g., such as a minimum/maximum data network throughput, a minimum delay requirement, a packet loss rate, and a packet download time, etc.) in a wireless communications system.
Presently, several scheduler algorithms have been proposed. One algorithm is termed a proportional fair (PF) scheduler algorithm. The principal of the PF algorithm is to schedule users for transmission with a maximum data rate channel (DRC) requested-to-average throughput ratio, which is also referred to as the priority weight of each user. In telecommunications, throughput means bits of information received per second. A user perceived throughput in the system is defined as the average information bits received by a user per second. In mathematical form, this ratio may be expressed by the following expression:
                                          max            i                    ⁢                                                    DRC                i                            ⁡                              (                n                )                                                                    R                i                            ⁡                              (                n                )                                                    ,                                  ⁢                              where            ⁢                                                  ⁢                                          R                i                            ⁡                              (                n                )                                              =                                                    (                                  1                  -                                      1                    T                                                  )                            ⁢                                                R                  i                                ⁡                                  (                                      n                    -                    1                                    )                                                      +                                          1                T                            ⁢                                                                    DRC                    i                    assigned                                    ⁡                                      (                    n                    )                                                  .                                                                        (        1        )            
In expression (1), DRCi(n) is the DRC value requested by user i at time instant n. DRCiassigned is the DRC value assigned to user i at time instant n. Ri(n) is the i-th user throughput averaged by an IIR filter with time constant T. The time constant T is a time scale over which the average throughput is measured. The fairness principal is also based on time constant T. The choice of T should be sufficiently large to smooth out fluctuations of fading channels, and to represent an average channel condition perceived by a user, but not too large to meet or exceed packet delay requirements.
The PF algorithm explores a multiplexing gain from multiple users, and at the same time serves users in what is called a “proportional fair” sense. The PF algorithm tends to equalize the DRCi(n)/Ri(n) ratio among users. As a result, the average user throughput will be “proportional to” the DRC rate a user has requested, or Ri∝DRCi. In other words, a user having a good channel condition will achieve a good throughput, and for a user with poor channel condition, a poor throughput. Moreover, the PF algorithm is a generic algorithm which does not take care of QoS requirements that may be imposed by the system. Additionally, the PF algorithm requires much guess work and is not fully implemented for user diversity.
Another algorithm, called a generalized proportional fairness algorithm or G-Fair algorithm, is a generalized version of the PF algorithm that has been created to further explore user diversity. The algorithm may be defined by the following expression;
                              max          i                ⁢                                                            DRC                i                            ⁡                              (                n                )                                                                    R                i                            ⁡                              (                n                )                                              *                                    h              ⁡                              (                                  DRC                  i                  avg                                )                                                    DRC              i              avg                                                          (        2        )            where DRCi(n),
            DRC      i      assigned        ⁡          (      n      )        ,and Ri(n) have the same definitions as stated in Equation (1); and where
      DRC    i    avg    ⁡      (    n    )  is the averaged DRC value of user i at time instant n, and is updated using the following expression:
                                          DRC            i            avg                    ⁡                      (            n            )                          =                                            (                              1                -                                  1                  T                                            )                        ⁢                                          DRC                i                avg                            ⁡                              (                                  n                  -                  1                                )                                              +                                    1              T                        ⁢                                                            DRC                  i                  assigned                                ⁡                                  (                  n                  )                                            .                                                          (        3        )            
The priority weight computation in the G-Fair algorithm differs from the PF algorithm by multiplying the original weighting value with a function h(DRCiavg)/DRCiavg. There are five different variations of function h( ), which lead to five different options for G-Fair algorithms:
                                                                        Option 0:                            ⁢                                                          ⁢                              h                ⁡                                  (                                      DRC                    i                    avg                                    )                                                      =                          DRC              i              avg                                ;                ⁢                                                                                                                          Option 1:                        ⁢                                                  ⁢            h            ⁢                          (                              DRC                i                avg                            )                                =                      2            *                          DRC              i              avg                                      ;                                                                                                Option 2:                        ⁢                                                  ⁢            h            ⁢                          (                              DRC                i                avg                            )                                =                      4            *                          DRC              i              avg                                      ;                                                                                                                Option 3:                            ⁢                                                          ⁢              h              ⁢                              (                                  DRC                  i                  avg                                )                                      =            1                    ;                ⁢                                                                                                            Option 4:                    ⁢                                          ⁢          h          ⁢                      (                          DRC              i              avg                        )                          =                              min            ⁡                          (                                                c                  *                                      DRC                    i                    avg                                                  ,                d                            )                                .                                                
In Options 0-4,
  DRC  i  avgis the average DRC value in units of 150 bps of the i-th user, c is a constant, and d is a constant with a valid range between 256-16384. The constant c maybe set to 1 to simplify the above expression (3). Option 0, Option 1 and Option 2, though each in a different form, all lead to a PF algorithm in terms of their performance because all users' priorities are scaled by the same fixed constant and the order of priorities remain unchanged. In Option 3, where h( )=1, the constant “1” on the right hand side of the expression may be replaced by other constants without affecting the performance of Option 3. The scheduling principle in Option 3 is different from the scheduling principles of the PF algorithm. Instead of providing a user throughput that is proportional to a user's requests, as suggested by the PF algorithm, Option 3 provides a user throughput that is proportional to the variation of a user's requests over time.
Option 4 is a generalized form of the G-Fair algorithm. Option 4 will degenerate into Option 3 with a small d value, and become Options 0, 1, and 2 with a large d value. The performance of Option 4 is dictated by the ratio of the two parameters, constant c and constant d, but not their absolute values. For instance, in comparing a situation where {c=1, d=256} and a situation where {c=2, d=512} each result in the same performance. To further simplify the expression (3), the parameter c is normalized to equal one (c=1). Since Option 4 encompasses other options of the G-Fair algorithm, the following discussion focuses primarily on Option 4 of the G-Fair algorithm.
FIG. 1 illustrates performance of a conventional scheduler algorithm. Specifically, the h-function of Option 4 of the G-Fair algorithm consists of two fragments of straight lines, as illustrated in FIG. 1. For
  DRC  i  avgvalues less than d, the weight computation in equation (2) reduces to equation (1) of PF algorithm. For DRCiavg values greater than d,
  h  ⁡      (          DRC      i      avg        )  values is capped at d, and the weight computed in equation (2) will be a smaller value than as computed in PF algorithm. This behavior of h-function provides a control mechanism to discourage users with high
      DRC    i    avg    ,so as to benefit a user having a poor
      DRC    i    avg    .With a properly chosen d value, the dynamic ranges of user perceived throughputs, the distance range between the minimum and the maximum throughputs, can be adjusted as well.
The performance of the G-Fair algorithm was simulated based on the assumptions listed in Table 1. For the stimulation, 20 simultaneous active mobiles at 3 kmph with full buffer data to transmit where evaluated. Three propagation channel conditions were simulated, including additive white gaussian noise (AWGN), 1-path Rayleigh fading and 2-path Rayleigh fading. The values of parameter d in the h-function were chosen as multiples of 256, such that the corresponding physical channel rates were multiples of 38.4 kbps.
TABLE 1G-Fair Algorithm Simulation Assumptions.Number of mobiles 20mobile Speed3 kmphPropagation ChannelsAWGN, 1-path, 2-pathTraffic ModelFull Buffer TransmissionIIR Filter Time Const T1024h-function Parameter d256(38.4 kbps),512(76.8 kbps),1024(153.6 kbps),2048(307.2 kbps),4096(614.4 kbps),8192(1.2 Mbps),16384(2.4 Mbps)
FIG. 2 illustrates the performance of the conventional scheduler algorithm of FIG. 1 for different user throughputs. Specifically, FIG. 2 illustrates the performance of the G-Fair algorithm in terms of user throughputs and sector throughputs. A user throughput characterizes the user-perceived channel rate, and is embodied as a ratio of the total successfully received bits by a user on a physical to the session active time. The sector throughput is the aggregate channel rate per sector. A coverage area served by one BS is called a cell; within a cell, there might be multiple sectors. The typical configuration is to have three sectors in one cell. The sector throughput is computed as the ratio of the total good physical channel transmitted bits to the simulation time.
A standard deviation of user throughput can be considered a measure of “fairness”. As shown in FIG. 2, as the value of parameter d varies between 256 to 16384, the standard deviation of user throughput ranges from about 0 to 45 kbps, and the sector throughput ranges from about 400 to 1000 kbps. The standard deviation of the user throughout decreases as the value of parameter d decreases. A small value of d can be used to provide uniform user throughput independent of different channel conditions of individual users. However, the tradeoff to reducing d results in a reduced sector throughput, because the scheduler does not fully explore good channel conditions seen by some users. The scheduler treats all users as if they had the same channel conditions. However, by properly choosing parameter d, a certain degree of fairness may be achieved, albeit with a compromised sector throughput.
The G-Fair algorithm, much as the PF algorithm, is a generic algorithm which would require extensive modification as more requirements are imposed on the wireless system, such as the aforementioned QoS requirements. For instance, in order to impose minimum or maximum rate QoS requirements, the scheduler needs to define an objective variable that is a function of QoS variables. There is no mechanism in presently proposed scheduler algorithm(s) that enable the scheduler to handle the increasing QoS requirements of third generation wireless systems.
Moreover, even though the G-Fair algorithm, much as the PF algorithm, attempts to allocate communication resources among multiple users more fairly than would a simple first-come-first-served queuing algorithm, such allocations, however, do not provide providers of wireless communication services with sufficient control over data transmission to meet all service provider requirements (QoS requirements). There remains, for example, a problem of constraining the data throughput of those users that put excessive demands on a wireless communications network. There is also the problem of differentiating among users on the basis of the nature of the application for which each user is utilizing the network. Further, there is the problem of differentiating among network users on the basis of individual users' payment plans. Thus, conventional schemes for allocating the transmission of data do not adequately address these and other service provider requirements.